3. 无重复字符的最长子串

Similar Question

leading to the advanced question

Solution Tips

方案一: 滑动窗口 + 哈希

窗口的数据结构是哈希集合

var lengthOfLongestSubstring = function(s) {
    // 哈希集合，记录每个字符是否出现过
    const occ = new Set();
    const n = s.length;
    // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
    let rk = -1, ans = 0;
    for (let i = 0; i < n; ++i) {
        if (i != 0) {
            // 左指针向右移动一格，移除一个字符
            occ.delete(s.charAt(i - 1));
        }
        while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) {
            // 不断地移动右指针
            occ.add(s.charAt(rk + 1));
            ++rk;
        }
        // 第 i 到 rk 个字符是一个极长的无重复字符子串
        ans = Math.max(ans, rk - i + 1);
    }
    return ans;
};

方案二: 优化的滑动窗口

上述的方法最多需要执行 2n 个步骤。事实上，它可以被进一步优化为仅需要 n 个步骤。我们可以定义字符到索引的映射，而不是使用集合来判断一个字符是否存在。 当我们找到重复的字符时，我们可以立即跳过该窗口。

也就是说，如果 s[j] 在 [i, j) 范围内有与 索引 j' 重复的字符，我们不需要逐渐增加 i 。 我们可以直接跳过 [i，j'] 范围内的所有元素，并将 i 变为 j'+1。

因为以 [i, j') 范围内每一个字符开头的最长的子串，都会在 j 处与 j' 重复，所以我们直接从 j'+1 开始即可

  var lengthOfLongestSubstring = function (s) {
    const map = new Map();
    let max = 0;
    for (let i = 0, j = 0; j < s.length; j++) {
      if (map.has(s[j])) {
        // 有重复时 i 从 j'+1 处开始
        i = Math.max(map.get(s[j]) + 1, i);
      }
      // 如果重复了也要更新s[j]的值，所以在判断外执行该语句
      map.set(s[j], j);
      max = Math.max(max, j - i + 1);
    }
    return max;
  };